1. Field of the Invention
The present invention relates generally to a communication system using Low-Density Parity-Check (LDPC) codes, and more particularly, to a channel encoding/decoding apparatus and method for generating LDPC codes having various codeword lengths and code rates from an LDPC code given in a high-order modulation scheme.
2. Description of the Related Art
In wireless communication systems, link performance significantly decreases due to various noises in the channels, a fading phenomenon, and Inter-Symbol Interference (ISI). Therefore, in order provide high-speed digital communication systems, which require high data throughput and reliability, such as the next-generation mobile communication, digital broadcasting, and portable internet, it is important to develop technologies for overcoming the channel noises, fading, and ISI. Recently, an intensive study of an error-correcting code has been conducted as a method for increasing communication reliability by efficiently recovering distorted information.
The LDPC code, i.e., a type of error-correcting code, is generally defined as a parity-check matrix, and can be represented using a bipartite graph, which is referred to as a Tanner graph. The bipartite graph means that vertexes constituting the graph are divided into two different types, and the LDPC code is represented with the bipartite graph composed of vertexes, some of which are called variable nodes and the other of which are called check nodes. The variable nodes are one-to-one mapped to the encoded bits.
FIG. 1 illustrates an example of a parity-check matrix H1 of the LDPC code having 4 rows and 8 columns.
Referring to FIG. 1, because the number of columns is 8, the parity-check matrix H1 is an LDPC code that generates a length-8 codeword, and the columns are mapped to 8 encoded bits.
FIG. 2 illustrates a Tanner graph corresponding to the parity-check matrix H1 of FIG. 1.
Referring to FIG. 2, the Tanner graph of the LDPC code includes 8 variable nodes x1 (202), x2 (204), x3 (206), x4 (208), x5 (210), x6 (212), x7 (214), and x8 (216), and 4 check nodes 218, 220, 222, and 224. An ith column and a jth row in the parity-check matrix H1 of the LDPC code are mapped to a variable node xi and a jth check node, respectively. In addition, a value of 1, i.e., a non-zero value, at the point where an ith column and a jth row in the parity-check matrix H1 of the LDPC code cross each other, indicates that there is an edge between the variable node xi and the jth check node on the Tanner graph as illustrated in FIG. 2.
In the Tanner graph of the LDPC code, a degree of the variable node and the check node indicates the number of edges connected to each respective node, and the degree is equal to the number of non-zero entries in a column or row corresponding to the pertinent node in the parity-check matrix of the LDPC code. For example, in FIG. 2, degrees of the variable nodes x1 (202), x2 (204), x3 (206), x4 (208), x5 (210), x6 (212), x7 (214), and x8 (216) are 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and degrees of check nodes 218, 220, 222, and 224 are 6, 5, 5, and 5, respectively. In addition, the numbers of non-zero entries in the columns of the parity-check matrix H1 of FIG. 1, which correspond to the variable nodes of FIG. 2, coincide with their degrees 4, 3, 3, 3, 2, 2, 2, and 2, respectively, and the numbers of non-zero entries in the rows of the parity-check matrix H1 of FIG. 1, which correspond to the check nodes of FIG. 2, coincide with their degrees 6, 5, 5, and 5, respectively.
In order to express degree distribution for the nodes of the LDPC code, a ratio of the number of degree-i variable nodes to the total number of variable nodes is defined as fi, and a ratio of the number of degree-j check nodes to the total number of check nodes is defined as gj. For example, for the LDPC code corresponding to FIGS. 1 and 2, f2= 4/8, f3=⅜, f4=⅛, and fi=0 for i≠2, 3, 4; and g5=¾, g6=¼, and gj=0 for j≠5, 6. When a length of the LDPC code, i.e., the number of columns, is defined as N, and the number of rows is defined as N/2, the density of non-zero entries in the entire parity-check matrix having the above degree distribution is computed as shown Equation (1).
                                                        2              ⁢                              f                2                            ⁢              N                        +                          3              ⁢                              f                3                            ⁢              N                        +                          4              ⁢                              f                4                            ⁢              N                                            N            ·                          N              /              2                                      =                  5.25          N                                    (        1        )            
In Equation (1), as N increases, the density of 1's in the parity-check matrix decreases. Generally, as for the LDPC code, because the codeword length N is inversely proportional to the density of non-zero entries, the LDPC code with a large N has a very low density of non-zero entries. The term “low-density” in the name of the LDPC code originates from the above-mentioned relationship.
FIG. 3 schematically illustrates an LDPC code adopted as the standard technology in Digital Video Broadcasting-Satellite transmission 2nd generation (DVB-S2), which is one of the European digital broadcasting standards.
In FIG. 3, N1 and K1 denote a codeword length and an information length (or length of information word) of an LDPC code, respectively, and (N1−K1) provides a parity length. Further, integers M1 and q satisfy q=(N1−K1)/M1. Preferably, K1/M1 is an integer.
Referring to FIG. 3, a structure of a parity part, i.e., K1th column through (N1−1)th column, in the parity-check matrix, has a dual diagonal shape. Therefore, as for degree distribution over columns corresponding to the parity part, all columns have a degree of 2, except for the last column having a degree of 1.
In the parity-check matrix, an information part, i.e., 0th column through (K1−1)th column, is created using the following rules.
Rule 1: A total of K1/M1 column groups is generated by grouping K1 columns corresponding to the information word in the parity-check matrix into multiple groups each including M1 columns. A method for forming columns belonging to each column group follows Rule 2 below.
Rule 2: First, positions of 1's in each 0th column in ith column groups (where i=1, . . . ,K1/M1) are determined. When a degree of a 0th column in each ith column group is denoted by Di, if positions of rows with 1 are assumed to be Ri,0(1),Ri,0(2), . . . ,Ri,0Di), positions Ri,j(k)(k=1,2, . . . ,Di) of rows with 1 are defined as shown in Equation (2), in a jth column (where j=1,2, . . . ,M1−1) in an ith column group.Ri,j(k)=Ri,(j−1)(k)+q mod(N1−K1),k=1,2, . . . ,Di, i=1, . . . ,K1/M1, j=1, . . . ,M1−1   (2)
According to the above rules, it can be appreciated that degrees of columns belonging to an ith column group are all equal to Di. For a better understanding of a structure of a DVB-S2 LDPC code that stores information on the parity-check matrix according to the above rules, the following more detailed example will be given.
As a detailed example, for N1=30, K1=15, M1=5, and q=3, three sequences for the information on the positions of rows with 1 for 0th columns in 3 column groups can be expressed as follows. Herein, these sequences are referred to as “weight-1 position sequences.”R1,0(1)=0, R1,0(2)=1, R1,0(3)=2,R2,0(1)=0, R2,0(2)=11, R2,0(3)=13,R3,0(1)=0, R3,0(2)=10, R3,0(3)=14.
Regarding the weight-1 position sequence for 0th columns in each column group, only the corresponding position sequences can be expressed as follows for each column group. For example:
0 1 2
0 11 13
0 10 14.
That is, the ith weight-1 position sequence in the ith line sequentially represents the information on the positions of rows with 1 for the ith column group.
It is possible to generate an LDPC code having the same concept as that of a DVB-S2 LDPC code illustrated FIG. 4, by forming a parity-check matrix using the information corresponding to the detailed example, and Rules 1 and 2.
It is known that the DVB-S2 LDPC code designed in accordance with Rules 1 and 2 can be efficiently encoded using the structural shape. Respective steps in a process of performing LDPC encoding using the DVB-S2 based parity-check matrix will be described below by way of example.
In the following description, as a detailed example, a DVB-S2 LDPC code with N1=16200, K1=10800, M1=360, and q=15 undergoes an encoding process. For convenience, information bits having a length K1 are represented as (i0,i1, . . . ,iK1−1), and parity bits having a length (N1−K1) are expressed as (p0,p1, . . . ,pN1−K1−1).
Step 1: An LDPC encoder initializes parity bits as follows:
p0=p1= . . . =pN1−K1−1=0
Step 2: The LDPC encoder reads information on rows where a 1 is located in a column group from a 0th weight-1 position sequence out of the stored sequences indicating the parity-check matrix.
0 2084 1613 1548 1286 1460 3196 4297 2481 3369 3451 4620 2622R1,0(1)=0, R1,0(2)=2048, R1,0(3)=1613, R1,0(4)=1548, R1,0(5)=1286,R1,0(6)=1460, R1,0(7)=3196, R1,0(8)=4297, R1,0(9)=2481, R1,0(10)=3369,R1,0(11)=3451, R1,0(12)=4620, R1,0(13)=2622.
The LDPC encoder updates particular parity bits px in accordance with Equation (3), using the read information and the first information bit i0. Herein, x is a value of R1,0(k) for k=1, 2, . . . ,13.p0=p0⊕i0, p2084=p2064⊕i0, p1613=p1613⊕i0,p1548=p1548⊕i0, p1286=p1286⊕i0, p1460=p1460⊕i0,p3196=p3196⊕i0, p4297=p4297⊕i0, p2481=p2481⊕i0,   (3)p3369=p3369l ⊕i0, p3451=p3451⊕i0, p4620⊕i0,p2622=p2622⊕i0 
In Equation (3), px=px⊕i0 can also be expressed as px←px⊕i0, and ⊕ represents binary addition.
Step 3: The LDPC encoder determines a value of Equation (4) for the next 359 information bits im (where m=1, 2, . . . , 359) after i0.{x+(m mod M1)×q}mod(N1−K1), M1=360, m=1,2, . . . ,359   (4)
In Equation (4), x is a value of R1,0(k) for k=1,2, . . . , 13. It should be noted that Equation (4) has the same concept as Equation (2).
Next, the LDPC encoder performs an operation similar to Equation (3) using the values found in Equation (4). That is, the LDPC encoder updates parity bits P{x+(m mod M1)×q}mod(N1−K1) for im. For example, for m=1, i.e., for i1, the LDPC encoder updates parity bits p(x+q)mod(N1−K1) as defined in Equation (5).p15=p15⊕i1, p2099=p2099⊕i1, p1628=p1628⊕i1,p1563=p1563⊕i1, p1301=p1301⊕i1, p1475=p1475⊕i1,p3211=p3211⊕i1, p4312=p4312⊕i1, p2496=p2496⊕i1,   (5)p3384=p3384⊕i1, p3466=p3466⊕i1, p4635=p4635⊕i1,p2637=p2637⊕i1 
In Equation (5), q=15. The LDPC encoder performs the above process for m=1, 2, . . . , 359, in the same manner as described above.
Step 4: As in Step 2, the LDPC encoder reads information of the 1st weight-1 position sequence R2,0(k) (k=1, 2, . . . , 13) for a 361st information bit i360, and updates a particular px, where x is R2,0(k). The LDPC encoder updates p{x+(m mod M1)×q}mod(N1−K1), m=361,362, . . . ,719 by similarly applying Equation (4) to the next 359 information bits i361, i362, . . . , i719 after i360.
Step 5: The LDPC encoder repeats Steps 2, 3, and 4 for all groups each having 360 information bits.
Step 6: The LDPC encoder finally determines parity bits using Equation (6).pi=pi⊕pi−1, i=1,2, . . . ,N1−K1−1   (6)
The parity bits pi of Equation (6) have undergone LDPC encoding.
As described above, DVB-S2 performs encoding as described in Steps 1 to 6.
In order to apply the LDPC code to the actual communication system, the LDPC code should be designed to be suitable for the data rate required in the communication system. Particularly, LDPC codes having various codeword lengths are needed to support various data rates according to the system requirements in an adaptive communication system employing Hybrid Automatic Retransmission reqQuest (HARQ) and Adaptive Modulation and Coding (AMC), and also in a communication system supporting various broadcast services.
However, as described above, the LDPC code used in the DVB-S2 system has only two types of codeword lengths due to its limited use, and each type of the LDPC code uses an independent parity-check matrix. Accordingly, there is a long-felt need in the art for a method for supporting various codeword lengths to increase extendibility and flexibility of the system. Particularly, in the DVB-S2 system, transmission of data having several hundreds to thousands of bits is needed for transmitting signaling information. However, because only 16200 and 64800 are available for a length of the DVB-S2 LDPC code, there is a still a need for support of various codeword lengths. However, because storing independent parity-check matrixes for respective codeword lengths of the LDPC code may reduce memory efficiency, there is also a need for a scheme capable of efficiently supporting various codeword lengths from the existing parity-check matrix, without requiring a new parity-check matrix.
It is noted that reliabilities of bits included in high-order modulation symbols are different when high-order modulation is used in the communication system requiring an LDPC code with various codeword lengths, unlike when the high-order modulation is applied in the communication system employing only Binary Phase Shift Keying (BPSK) or Quadrature Phase Shift Keying (QPSK).
In order to demonstrate the reliability difference in high-order modulation, a description will now be made below as to signal constellations for Quadrature Amplitude Modulation (QAM), which is high-order modulation commonly used in communication systems. A QAM-modulated symbol includes a real part and an imaginary part, and various modulation symbols can be generated by differentiating magnitudes and signs of their real parts and imaginary parts. QAM will be described together with QPSK modulation in order to more clearly provide the details of QAM characteristics.
FIG. 5A schematically illustrates a signal constellation for a conventional QPSK modulation.
Referring to FIG. 5A, y0 determines a sign of a real part while y1 determines a sign of an imaginary part. That is, a sign of the real part is plus (+) for y0=0, and minus (−) for y0=1. Also, a sign of the imaginary part is plus (+) for y1=0, and minus (−) for y1=1. Because y0 and y1 are equal in error occurrence probability, as they are sign indication bits that respectively indicate signs of the real part and the imaginary part, reliabilities of (y0, y1) bits corresponding to one modulation signal are equal in QPSK modulation. For y0,q and y1,q, the second subscript index q indicates a qth output of bits included in a modulation signal.
FIG. 5B schematically illustrating a signal constellation for a conventional 16-QAM modulation.
Referring to FIG. 5B, (y0, y1, y2, y3) correspond to bits of one modulation signal. More specifically, bits y0 and y2 determine a sign and a magnitude of the real part, respectively, while bits y1 and y3 determine a sign and a magnitude of the imaginary part, respectively. That is, y0 and y1 determine signs of the real part and imaginary part of the modulation signal, while y2 and y3 determine magnitudes of the real part and imaginary part of the modulation signal. Because distinguishing a sign of a modulated signal is easier than distinguishing a magnitude of the modulated signal, y2 and y3 are higher in error occurrence probability than y0 and y1. Therefore, in terms of non-error occurrence probabilities (i.e., reliabilities) of the bits, y0=y1>y2=y3. That is, bits (y0, y1, y2, y3), which are included in a QAM modulation signal, unlike those of a QPSK modulation signal, have different reliabilities.
In 16-QAM modulation, among 4 bits constituting a signal, 2 bits determine signs of the real part and imaginary part of the signal and the remaining 2 bits only need to determine magnitudes of the real part and imaginary part of the signal. Thus, orders of (y0, y1, y2, y3) and a role of each bit are subject to change.
FIG. 5C schematically illustrates a signal constellation for a conventional 64-QAM modulation.
From among (y0, y1, y2, y3, y4, y5), which correspond to bits of one modulation signal, bits y0, y2, and y4 determine a magnitude and a sign of the real part, and y1, y3, and y5 determine a magnitude and a sign of the imaginary part. Here, y0 and y1 determine signs of the real part and the imaginary part, respectively, and a combination of y2 and y4 and a combination of y3 and y5 determine magnitudes of the real part and the imaginary part, respectively. As described above, because distinguishing signs of a modulated signal is easier than distinguishing magnitudes of the modulated signal, reliabilities of y0 and y1 are higher than reliabilities of y2, y3, y4, and y5.
The bits y2 and y3 are determined depending on whether a magnitude of the modulated symbol is greater or less than 4, and the bits y4 and y5 are determined according to whether the magnitude of the modulated symbol is closer to 4 or 0, with 2 centered therebetween, or closer to 4 or 8 with 6 centered. Accordingly, a range in which the magnitude is determined by y2 and y3 is 4, while a range for y4 and y5 is 2. Therefore, y2 and y3 is higher than y4 and y5 in reliability. As a result, y0=y1>y2=y3>y4=y5 in terms of non-error occurrence probabilities (i.e., reliabilities) of the bits.
In 64-QAM modulation, of 6 bits constituting a signal, 2 bits determine signs of the real part and imaginary part of the signal and 4 bits only need to determine magnitudes of the real part and imaginary part of the signal. Accordingly, orders of (y0, y1, y2, y3, y4, y5) and a role of each bit are subject to change. Even in a signal constellation of 256-QAM or higher, the roles and reliabilities of bits constituting a modulation signal are different as described above. Accordingly, a detailed description thereof is to be omitted herein.
To summarize, in BPSK or QPSK modulation, it is not necessary to consider a modulation scheme when determining shortening and puncturing patterns because as reliabilities of bits included in a symbol are equal, reliabilities of codeword bits are also equal in an LDPC codeword that has undergone shortening or puncturing. However, in high-order modulation such as 16-QAM, 64-QAM, and 256-QAM, because the roles and reliabilities of bits included in a symbol are different, when a modulation scheme and a signal constellation/bit mapping (bit mapping on the signal constellation) scheme have been determined, reliability of each codeword bit in an LDPC codeword, after it undergoes shortening or puncturing, may be different from that of the LDPC codeword before it undergoes shortening or puncturing.
Therefore, there is a demand for an apparatus and method for generating an LDPC code using shortening or puncturing in consideration of high-order modulation.